被围绕的区域

[编程题]被围绕的区域

热度指数：2246 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个 n*m 大小的的矩阵，矩阵中由 ‘X' 和 'O' 构成，找到所有被 'X' 围绕的区域，并将其用 'X' 填充。

例如：

[['X','X','X','X'],

['X','O','O','X'],

['X','O','X','X'],

['X','X','O','X']]

中间的三个 ‘O’ 被 'X'围绕，因此将其填充为 'X' ，但第四行的 'O' 下方没有被 'X' 围绕，因此不改变，结果为

[['X','X','X','X'],

['X','X','X','X'],

['X','X','O','X']]

数据范围： $1 \le n , m \le 200 \$ ，矩阵中保证只含有 'X' 和 'O'

示例1

输入

[[X,X,X,X],[X,O,O,X],[X,O,X,X],[X,X,O,X]]

输出

[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,X,O,X]]

示例2

输入

[[O]]

输出

[[O]]

备注:

算法知识视频讲解

Python 3

梅子酒l

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param board char字符型二维数组 
# @return char字符型二维数组
#
class Solution:
    def dfs(self, num, i, j):
        if num[i][j] == 'O':
            num[i][j] = 1
            x1 = [0,0,1,-1]
            y1 = [1,-1,0,0]
            for k in range(4):
                x = x1[k]+i 
                y = y1[k]+j
                if 0 <= x < len(num) and 0 <= y < len(num[0]) and num[x][y] == 'O':
                    self.dfs(num, x, y)
        return num
    
    
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        m = len(board)
        n = len(board[0])
        if m > 2 and n > 2:
            for i in range(m):
                for j in range(n):
                    if i == 0&nbs***bsp;j == 0&nbs***bsp;i == m-1&nbs***bsp;j == n-1:
                        board = self.dfs(board, i, j)
            for i in range(m):
                for j in range(n):
                    if board[i][j] == 1:
                        board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'
            return board
        else:
            return board

发表于 2022-08-25 19:03:15 回复(0)

Python 3

Blind201904102241277

BFS解法

class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here

        m = len(board)
        n = len(board[0])

        def is_valid(x, y):
            return 0<=x<m and 0<=y<n

        def bfs(i, j, from_sig, to_sig):
            q = []
            q.append((i, j))
            board[i][j] = to_sig
            while q:
                sz = len(q)
                for _ in range(sz):
                    i, j = q.pop(0)
                    for di, dj in [[1,0],[0,1],[-1,0],[0,-1]]:
                        new_i, new_j = i+di, j+dj
                        if is_valid(new_i, new_j) and board[new_i][new_j] == from_sig:
                            q.append((new_i, new_j))
                            board[new_i][new_j] = to_sig

        for i in range(m):
            for j in range(n):
                if (i == 0&nbs***bsp;i == m-1&nbs***bsp;j == 0&nbs***bsp;j == n-1) and board[i][j] == "O":
                    bfs(i, j, "O", "SB")

        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    bfs(i, j, "O", "X")
        for i in range(m):
            for j in range(n):
                if board[i][j] == "SB":
                    bfs(i, j, "SB", "O")
                    
        return board

发表于 2022-06-30 20:35:24 回复(0)

Python 3

Joy_9

class Solution:
    def surroundedArea(self , board: List[List[str]]) -> List[List[str]]:
        # write code here
        m,n=len(board),len(board[0])
        def dfs(i,j):
            if (i<0&nbs***bsp;i>m-1)&nbs***bsp;(j<0&nbs***bsp;j>n-1)&nbs***bsp;board[i][j]!="O":
                return
            if board[i][j]=="O":
                board[i][j]="No"
            dfs(i-1,j)
            dfs(i+1,j)
            dfs(i,j-1)
            dfs(i,j+1)
        for i in range(m):
            dfs(i,0)
            dfs(i,n-1)
        
        for j in range(n):
            dfs(0,j)
            dfs(m-1,j)
        for i in range(m):
            for j in range(n):
                if board[i][j]=="O":
                    board[i][j]="X"
                elif board[i][j]=="No":
                    board[i][j]="O"
        return board

发表于 2022-01-19 07:36:21 回复(0)